// 邻接矩阵
namespace Matrix {
	template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
	class Graph
	{
	public:
		Graph(const V* a, size_t n)
		{
			_vertex.reserve(n);
			for (size_t i = 0; i < n; i++)
			{
				_vertex.push_back(a[i]);
				_indexMap[a[i]] = i;
			}

			_matrix.resize(n);
			for (size_t i = 0; i < _matrix.size(); i++)
			{
				_matrix[i].resize(n, MAX_W);
			}
		}

		size_t GetVertexIndex(const V& v)
		{
			auto it = _indexMap.find(v);
			if (it != _indexMap.end())
			{
				return it->second;
			}
			else
			{
				throw invalid_argument("顶点不存在~");
				return -1;
			}
		}

		void AddEdge(const V& src, const V& dst, const W& w)
		{
			size_t srci = GetVertexIndex(src);
			size_t dsti = GetVertexIndex(dst);

			_matrix[srci][dsti] = w;
			if (Direction == false)
			{
				_matrix[dsti][srci] = w;
			}
		}

		void Print()
		{
			for (size_t i = 0; i < _vertex.size(); i++)
			{
				cout << '[' << i << ']' << "->" << '[' << _vertex[i] << ']' << endl;
			}
			cout << endl;
			
			cout << "  ";
			for (size_t i = 0; i < _matrix.size(); i++)
				cout << i << ' ';
			cout << endl;

			for (size_t i = 0; i < _matrix.size(); i++)
			{
				cout << i << ' ';
				for (size_t j = 0; j < _matrix[i].size(); j++)
				{
					if (_matrix[i][j] == MAX_W)
						cout << '*' << ' ';
					else 
						cout << _matrix[i][j] << ' ';
				}
				cout << endl;
			}
		}

	private:
		vector<V> _vertex;
		map<V, int> _indexMap;
		vector<vector<W>> _matrix;
	};

	void test()
	{
		Matrix::Graph<char, int, INT_MAX, true> g("0123", 4);
		g.AddEdge('0', '1', 1);
		g.AddEdge('0', '3', 4);
		g.AddEdge('1', '3', 2);
		g.AddEdge('1', '2', 9);
		g.AddEdge('2', '3', 8);
		g.AddEdge('2', '1', 5);
		g.AddEdge('2', '0', 3);
		g.AddEdge('3', '2', 6);

		g.Print();
	}
}

// 邻接表
namespace Link_table {
	template<class W>
	struct Edge
	{
		W _w;
		int _dsti;
		Edge<W>* _next;

		Edge(int dsti, const W& w) 
			:_dsti(dsti)
			,_w(w)
			,_next(nullptr)
		{}	
	};

	template<class V, class W, bool Direction = true>
	class Graph
	{
		typedef Edge<W> Edge;
	public:
		Graph(const V* a, size_t n)
		{
			_vertex.reserve(n);
			for (size_t i = 0; i < n; i++)
			{
				_vertex.push_back(a[i]);
				_indexMap[a[i]] = i;
			}

			_table.resize(n, nullptr);
		}

		size_t GetVertexIndex(const V& v)
		{
			auto it = _indexMap.find(v);
			if (it != _indexMap.end())
			{
				return it->second;
			}
			else
			{
				throw invalid_argument("顶点不存在~");
				return -1;
			}
		}

		void AddEdge(const V& src, const V& dst, const W& w)
		{
			size_t srci = GetVertexIndex(src);
			size_t dsti = GetVertexIndex(dst);

			Edge* e1 = new Edge(dsti, w);
			e1->_next = _table[srci];
			_table[srci] = e1;

			if (Direction == false)
			{
				Edge* e2 = new Edge(srci, w);
				e2->_next = _table[dsti];
				_table[dsti] = e2;
			}
		}

		void Print()
		{
			for (size_t i = 0; i < _vertex.size(); i++)
			{
				cout << '[' << i << ']' << "->" << '[' << _vertex[i] << ']' << endl;
			}
			cout << endl;

			for (size_t i = 0; i < _table.size(); i++)
			{
				cout << _vertex[i] << '[' << i << ']';
				Edge* e = _table[i];
				while (e)
				{
					cout << "->" << _vertex[e->_dsti] << '[' << e->_dsti << ']' << ':' << e->_w;
					e = e->_next;
				}
				cout << endl;
			}
		}

	private:
		vector<V> _vertex;
		map<V, int> _indexMap;
		vector<Edge*> _table;
	};

	void test()
	{
		string a[] = { "张三", "李四", "王五", "赵六" };
		Graph<string, int> g1(a, 4);
		g1.AddEdge("张三", "李四", 100);
		g1.AddEdge("张三", "王五", 200);
		g1.AddEdge("王五", "赵六", 30);

		g1.Print();
	}
}
